import numpy as np
from collections import Counter

# 计算欧几里得距离
def euclidean_distance(x1, x2):
    return np.sqrt(np.sum((x1 - x2)**2))
# KNN算法实现
class KNN:
    def __init__(self, k=3):
        self.k = k  # 近邻数  
    # 训练模型（KNN没有实际的训练过程，保存训练数据即可）
    def fit(self, X_train, y_train):
        self.X_train = X_train
        self.y_train = y_train
    # 预测分类
    def predict(self, X_test):
        predictions = [self._predict(x) for x in X_test]
        return np.array(predictions)
    # 单个样本预测
    def _predict(self, x):
        # 计算训练集中每个点与当前点的距离
        distances = [euclidean_distance(x, x_train) for x_train in self.X_train]
        # 获取距离最小的K个点的索引
        k_indices = np.argsort(distances)[:self.k]
        # 获取K个点对应的标签
        k_nearest_labels = [self.y_train[i] for i in k_indices]
        # 进行投票，返回最多票数的标签
        most_common = Counter(k_nearest_labels).most_common(1)
        return most_common[0][0]
